package com.zhz.leetcode.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * <p>
 * 两两比较
 * 比如 : {5, 6, 3, 1, 4, 2, 8, 7}
 * 5和6比较  不换位置 此时数组 : {5, 6, 3, 1, 4, 2, 8, 7}
 * 6和3比较  换位置  此时数组 : {5, 3, 6, 1, 4, 2, 8, 7}
 * 6和1比较  换位置  此时数组 : {5, 3, 1, 6, 4, 2, 8, 7}
 * 6和4比较  换位置  此时数组 : {5, 3, 1, 4, 6, 2, 8, 7}
 * 6和2比较  换位置  此时数组 : {5, 3, 1, 4, 2, 6, 8, 7}
 * 6和8比较 不换位置 此时数组 : {5, 3, 1, 4, 2, 6, 8, 7}
 * 8和7比较   换位置 此时数组 : {5, 3, 1, 4, 2, 6, 7, 8}
 *
 * 这样一轮之后，最大数会被换到最后一个，那么接下来，我们的遍历就可以少掉一位，就是最后一个数 8
 * 我们只需要遍历 nums[0 到 len-i-1]的位置。
 *
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] nums = {5, 6, 3, 1, 4, 2, 8, 7,1};
        BubbleSort m = new BubbleSort();
        m.sort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 冒泡排序
     */
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length-1; i++) {
            // 由于第一次的排序，已经可以将最大值放到最后一个位置去了
            // 所以下一次排序的时候可以忽略最后一个数据，不需要在比较了
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
    }


}
